package cn.bellychang.leetcode.question141;

/**
 * @author ChangLiang
 * @date 2020/11/2
 */
public class Solution {

    /**
     * Internally, pos is used to denote the index of the node that tail's next pointer is connected to.
     * Note that pos is not passed as a parameter.
     *
     * @param head
     * @return
     */
    public boolean hasCycle(ListNode head) {
        // 如何能够判断出是一个环 using O(1) space
        // 暴力破解
        // 循环不变量 head->..->curr 不是一个环
        while (head != null) {
            // 判断后面有没有node.next = index;
            ListNode temp = head.next;
            // 循环不变量 head后面的next指针没有再指向自身的
            while (temp != null) {
                if (temp == head) {
                    return true;
                }
                temp = temp.next;
            }
        }
        return false;
    }
}
